Abstract: We design and implement various algorithms for
solving the static RWA problem with the objective of minimizing
the maximum number of requested wavelengths based on LP
relaxation formulations. We present a link formulation, a path
formulation and a heuristic that breaks the problem in the two
constituent subproblems and solves them individually and
sequentially. The flow cost functions that are used in these
formulations result in providing integer optimal solutions despite
the absence of integrality constraints for a large subset of RWA
input instances, while also minimizing the total number of used
wavelengths. We present a random perturbation technique that is
shown to increase the number of instances for which we find
integer solutions, and we also present appropriate iterative fixing
and rounding methods to be used when the algorithms do not yield
integer solutions. We comment on the number of variables and
constraints these formulations require and perform extensive
simulations to compare their performance to that of a typical minmax
congestion formulation.
Abstract: Braess’s paradox states that removing a part of a network may im-
prove the players’ latency at equilibrium. In this work, we study the approxima-
bility of the best subnetwork problem for the class of random
G
n;p
instances
proven prone to Braess’s paradox by (Roughgarden and Valiant, RSA 2010) and
(Chung and Young, WINE 2010). Our main contribution is a polynomial-time
approximation-preserving reduction of the best subnetwork problem for such in-
stances to the corresponding problem in a simplified network where all neighbors
of
s
and
t
are directly connected by
0
latency edges. Building on this, we obtain
an approximation scheme that for any constant
" >
0
and with high probabil-
ity, computes a subnetwork and an
"
-Nash flow with maximum latency at most
(1+
"
)
L
+
"
, where
L
is the equilibrium latency of the best subnetwork. Our ap-
proximation scheme runs in polynomial time if the random network has average
degree
O
(poly(ln
n
))
and the traffic rate is
O
(poly(lnln
n
))
, and in quasipoly-
nomial time for average degrees up to
o
(
n
)
and traffic rates of
O
(poly(ln
n
))
.